package org.jheaps.array

import org.jheaps.Constants
import org.jheaps.DoubleEndedHeap
import org.jheaps.annotations.LinearTime
import org.jheaps.annotations.VisibleForTesting
import java.io.Serializable

/**
 * An array based binary MinMax heap. The heap is sorted according to the
 * [natural ordering][Comparable] of its keys, or by a
 * [Comparator] provided at heap creation time, depending on which
 * constructor is used.
 *
 *
 *
 * For details about the implementation see the following
 * [paper](http://doi.acm.org/10.1145/6617.6621):
 *
 *  * M. D. Atkinson, J.-R. Sack, N. Santoro, and T. Strothotte. Min-max Heaps
 * and Generalized Priority Queues. Commun. ACM, 29(10), 996--1000, 1986.
 *
 *
 *
 *
 * The implementation uses an array in order to store the elements and
 * automatically maintains the size of the array much like a
 * [java.util.Vector] does, providing amortized O(log(n)) time cost for
 * the `insert`, `deleteMin`, and `deleteMax` operations.
 * Operations `findMin` and `findMax` are worst-case O(1). The
 * bounds are worst-case if the user initializes the heap with a capacity larger
 * or equal to the total number of elements that are going to be inserted into
 * the heap.
 *
 *
 *
 * Constructing such a heap from an array of elements can be performed using the
 * method [.heapify] or [.heapify]
 * in linear time.
 *
 *
 *
 * Note that the ordering maintained by this heap, like any heap, and whether or
 * not an explicit comparator is provided, must be *consistent with
 * `equals`* if this heap is to correctly implement the `Heap`
 * interface. (See `Comparable` or `Comparator` for a precise
 * definition of *consistent with equals*.) This is so because the
 * `Heap` interface is defined in terms of the `equals` operation,
 * but this heap performs all key comparisons using its `compareTo` (or
 * `compare`) method, so two keys that are deemed equal by this method
 * are, from the standpoint of this heap, equal. The behavior of a heap
 * *is* well-defined even if its ordering is inconsistent with
 * `equals`; it just fails to obey the general contract of the
 * `Heap` interface.
 *
 *
 *
 * **Note that this implementation is not synchronized.** If
 * multiple threads access a heap concurrently, and at least one of the threads
 * modifies the heap structurally, it *must* be synchronized externally.
 * (A structural modification is any operation that adds or deletes one or more
 * elements or changing the key of some element.) This is typically accomplished
 * by synchronizing on some object that naturally encapsulates the heap.
 *
 * @param <K>
 * the type of keys maintained by this heap
 *
 * @author Dimitrios Michail
</K> */
class MinMaxBinaryArrayDoubleEndedHeap<K> : AbstractArrayHeap<K>, DoubleEndedHeap<K>, Serializable {
    /**
     * Constructs a new, empty heap, using the natural ordering of its keys.
     *
     *
     *
     * All keys inserted into the heap must implement the [Comparable]
     * interface. Furthermore, all such keys must be *mutually
     * comparable*: `k1.compareTo(k2)` must not throw a
     * `ClassCastException` for any keys `k1` and `k2` in the
     * heap. If the user attempts to put a key into the heap that violates this
     * constraint (for example, the user attempts to put a string key into a
     * heap whose keys are integers), the `insert(Object key)` call will
     * throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is [.DEFAULT_HEAP_CAPACITY] and
     * adjusts automatically based on the sequence of insertions and deletions.
     */
    constructor() : super(null, DEFAULT_HEAP_CAPACITY)

    /**
     * Constructs a new, empty heap, with a provided initial capacity using the
     * natural ordering of its keys.
     *
     *
     *
     * All keys inserted into the heap must implement the [Comparable]
     * interface. Furthermore, all such keys must be *mutually
     * comparable*: `k1.compareTo(k2)` must not throw a
     * `ClassCastException` for any keys `k1` and `k2` in the
     * heap. If the user attempts to put a key into the heap that violates this
     * constraint (for example, the user attempts to put a string key into a
     * heap whose keys are integers), the `insert(Object key)` call will
     * throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is provided by the user and is adjusted
     * automatically based on the sequence of insertions and deletions. The
     * capacity will never become smaller than the initial requested capacity.
     *
     * @param capacity
     * the initial heap capacity
     */
    constructor(capacity: Int) : super(null, capacity)

    /**
     * Constructs a new, empty heap, ordered according to the given comparator.
     *
     *
     *
     * All keys inserted into the heap must be *mutually comparable* by
     * the given comparator: `comparator.compare(k1,
     * k2)` must not throw a `ClassCastException` for any keys `k1`
     * and `k2` in the heap. If the user attempts to put a key into the
     * heap that violates this constraint, the `insert(Object key)` call
     * will throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is [.DEFAULT_HEAP_CAPACITY] and
     * adjusts automatically based on the sequence of insertions and deletions.
     *
     * @param comparator
     * the comparator that will be used to order this heap. If
     * `null`, the [natural ordering][Comparable] of
     * the keys will be used.
     */
    constructor(comparator: Comparator<in K?>?) : super(comparator, DEFAULT_HEAP_CAPACITY)

    /**
     * Constructs a new, empty heap, with a provided initial capacity ordered
     * according to the given comparator.
     *
     *
     *
     * All keys inserted into the heap must be *mutually comparable* by
     * the given comparator: `comparator.compare(k1,
     * k2)` must not throw a `ClassCastException` for any keys `k1`
     * and `k2` in the heap. If the user attempts to put a key into the
     * heap that violates this constraint, the `insert(Object key)` call
     * will throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is provided by the user and is adjusted
     * automatically based on the sequence of insertions and deletions.The
     * capacity will never become smaller than the initial requested capacity.
     *
     * @param comparator
     * the comparator that will be used to order this heap. If
     * `null`, the [natural ordering][Comparable] of
     * the keys will be used.
     * @param capacity
     * the initial heap capacity
     */
    constructor(comparator: Comparator<in K?>?, capacity: Int) : super(comparator, capacity)

    /**
     * Ensure that the array representation has the necessary capacity.
     *
     * @param capacity
     * the requested capacity
     */
    override fun ensureCapacity(capacity: Int) {
        checkCapacity(capacity)
        val newArray: Array<K?> = arrayOfNulls<Any>(capacity + 1) as Array<K?>
        System.arraycopy(array, 1, newArray, 1, size)
        array = newArray
    }

    /**
     * {@inheritDoc}
     */
    override fun findMax(): K {
        when (size) {
            0 -> throw NoSuchElementException()
            1 -> return array[1]!!
            2 -> return array[2]!!
            else -> if (comparator == null) {
                if ((array[3] as Comparable<K>).compareTo(array[2]!!) > 0) {
                    return array[3]!!
                } else {
                    return array[2]!!
                }
            } else {
                if (comparator.compare(array[3], array[2]) > 0) {
                    return array[3]!!
                } else {
                    return array[2]!!
                }
            }
        }
    }

    /**
     * {@inheritDoc}
     */
    override fun deleteMax(): K {
        val result: K?
        when (size) {
            0 -> throw NoSuchElementException()
            1 -> {
                result = array[1]
                array[1] = null
                size--
            }

            2 -> {
                result = array[2]
                array[2] = null
                size--
            }

            else -> if (comparator == null) {
                if ((array[3] as Comparable<K?>) > array[2]) {
                    result = array[3]
                    array[3] = array[size]
                    array[size] = null
                    size--
                    if (size >= 3) {
                        fixdownMax(3)
                    }
                } else {
                    result = array[2]
                    array[2] = array[size]
                    array[size] = null
                    size--
                    fixdownMax(2)
                }
            } else {
                if (comparator.compare(array[3], array[2]) > 0) {
                    result = array[3]
                    array[3] = array[size]
                    array[size] = null
                    size--
                    if (size >= 3) {
                        fixdownMaxWithComparator(3)
                    }
                } else {
                    result = array[2]
                    array[2] = array[size]
                    array[size] = null
                    size--
                    fixdownMaxWithComparator(2)
                }
            }
        }
        if (Constants.NOT_BENCHMARK) {
            if (2 * minCapacity < array.size - 1 && 4 * size < array.size - 1) {
                ensureCapacity((array.size - 1) / 2)
            }
        }

        return result!!
    }

    /**
     * Upwards fix starting from a particular element
     *
     * @param k
     * the index of the starting element
     */
    override fun fixup(k: Int) {
        if (onMinLevel(k)) {
            val p: Int = k / 2
            val kValue: K = array[ k ]!!
            if (p > 0 && (array[p] as Comparable<K>).compareTo(kValue) < 0) {
                array[ k ] = array[p]
                array[p] = kValue
                fixupMax(p)
            } else {
                fixupMin(k)
            }
        } else {
            val p: Int = k / 2
            val kValue: K = array[ k ]!!
            if (p > 0 && (kValue as Comparable<K>).compareTo(array[p]!!) < 0) {
                array[ k ] = array[p]
                array[p] = kValue
                fixupMin(p)
            } else {
                fixupMax(k)
            }
        }
    }

    /**
     * Upwards fix starting from a particular element
     *
     * @param k
     * the index of the starting element
     */
    override fun fixupWithComparator(k: Int) {
        if (onMinLevel(k)) {
            val p: Int = k / 2
            val kValue: K = array[ k ]!!
            if (p > 0 && comparator!!.compare(array[p], kValue) < 0) {
                array[ k ] = array[p]
                array[p] = kValue
                fixupMaxWithComparator(p)
            } else {
                fixupMinWithComparator(k)
            }
        } else {
            val p: Int = k / 2
            val kValue: K = array[ k ]!!
            if (p > 0 && comparator!!.compare(kValue, array[p]) < 0) {
                array[ k ] = array[p]
                array[p] = kValue
                fixupMinWithComparator(p)
            } else {
                fixupMaxWithComparator(k)
            }
        }
    }

    /**
     * Upwards fix starting from a particular element at a minimum level
     *
     * @param k
     * the index of the starting element
     */
    private fun fixupMin(k: Int) {
        var k: Int = k
        val key: K = array[ k ]!!
        var gp: Int = k / 4
        while (gp > 0 && (array[gp] as Comparable<K>).compareTo(key) > 0) {
            array[ k ] = array[gp]
            k = gp
            gp = k / 4
        }
        array[ k ] = key
    }

    /**
     * Upwards fix starting from a particular element at a minimum level.
     * Performs comparisons using the comparator.
     *
     * @param k
     * the index of the starting element
     */
    private fun fixupMinWithComparator(k: Int) {
        var k: Int = k
        val key: K = array[ k ]!!
        var gp: Int = k / 4
        while (gp > 0 && comparator!!.compare(array[gp], key) > 0) {
            array[ k ] = array[gp]
            k = gp
            gp = k / 4
        }
        array[ k ] = key
    }

    /**
     * Upwards fix starting from a particular element at a maximum level
     *
     * @param k
     * the index of the starting element
     */
    private fun fixupMax(k: Int) {
        var k: Int = k
        val key: K = array[ k ]!!
        var gp: Int = k / 4
        while (gp > 0 && (array[gp] as Comparable<K>).compareTo(key) < 0) {
            array[ k ] = array[gp]
            k = gp
            gp = k / 4
        }
        array[ k ] = key
    }

    /**
     * Upwards fix starting from a particular element at a maximum level.
     * Performs comparisons using the comparator.
     *
     * @param k
     * the index of the starting element
     */
    private fun fixupMaxWithComparator(k: Int) {
        var k: Int = k
        val key: K = array[ k ]!!
        var gp: Int = k / 4
        while (gp > 0 && comparator!!.compare(array[gp], key) < 0) {
            array[ k ] = array[gp]
            k = gp
            gp = k / 4
        }
        array[ k ] = key
    }

    /**
     * Downwards fix starting from a particular element.
     *
     * @param k
     * the index of the starting element
     */
    override fun fixdown(k: Int) {
        if (onMinLevel(k)) {
            fixdownMin(k)
        } else {
            fixdownMax(k)
        }
    }

    /**
     * Downwards fix starting from a particular element. Performs comparisons
     * using the comparator.
     *
     * @param k
     * the index of the starting element
     */
    override fun fixdownWithComparator(k: Int) {
        if (onMinLevel(k)) {
            fixdownMinWithComparator(k)
        } else {
            fixdownMaxWithComparator(k)
        }
    }

    /**
     * Downwards fix starting from a particular element at a minimum level.
     *
     * @param k
     * the index of the starting element
     */
    private fun fixdownMin(k: Int) {
        var k: Int = k
        var c: Int = 2 * k
        while (c <= size) {
            val m: Int = minChildOrGrandchild(k)
            if (m > c + 1) { // grandchild
                if ((array[m] as Comparable<K>).compareTo(array[ k ]!!) >= 0) {
                    break
                }
                var tmp = array[ k ]
                array[ k ] = array[m]
                array[m] = tmp
                if ((array[m] as Comparable<K>).compareTo(array[m / 2]!!) > 0) {
                    tmp = array[m]
                    array[m] = array[m / 2]
                    array[m / 2] = tmp
                }
                // go down
                k = m
                c = 2 * k
            } else { // child
                if ((array[m] as Comparable<K>).compareTo(array[ k ]!!) < 0) {
                    val tmp: K = array[ k ]!!
                    array[ k ] = array[m]
                    array[m] = tmp
                }
                break
            }
        }
    }

    /**
     * Downwards fix starting from a particular element at a minimum level.
     * Performs comparisons using the comparator.
     *
     * @param k
     * the index of the starting element
     */
    private fun fixdownMinWithComparator(k: Int) {
        var k: Int = k
        var c: Int = 2 * k
        while (c <= size) {
            val m: Int = minChildOrGrandchildWithComparator(k)
            if (m > c + 1) { // grandchild
                if (comparator!!.compare(array[m], array[ k ]) >= 0) {
                    break
                }
                var tmp = array[ k ]
                array[ k ] = array[m]
                array[m] = tmp
                if (comparator.compare(array[m], array[m / 2]) > 0) {
                    tmp = array[m]
                    array[m] = array[m / 2]
                    array[m / 2] = tmp
                }
                // go down
                k = m
                c = 2 * k
            } else { // child
                if (comparator!!.compare(array[m], array[ k ]) < 0) {
                    val tmp = array[ k ]
                    array[ k ] = array[m]
                    array[m] = tmp
                }
                break
            }
        }
    }

    /**
     * Downwards fix starting from a particular element at a maximum level.
     *
     * @param k
     * the index of the starting element
     */
    private fun fixdownMax(k: Int) {
        var k: Int = k
        var c: Int = 2 * k
        while (c <= size) {
            val m: Int = maxChildOrGrandchild(k)
            if (m > c + 1) { // grandchild
                if ((array[m] as Comparable<K>).compareTo(array[ k ]!!) <= 0) {
                    break
                }
                var tmp = array[ k ]
                array[ k ] = array[m]
                array[m] = tmp
                if ((array[m] as Comparable<K>).compareTo(array[m / 2]!!) < 0) {
                    tmp = array[m]
                    array[m] = array[m / 2]
                    array[m / 2] = tmp
                }
                // go down
                k = m
                c = 2 * k
            } else { // child
                if ((array[m] as Comparable<K>).compareTo(array[ k ]!!) > 0) {
                    val tmp = array[ k ]
                    array[ k ] = array[m]
                    array[m] = tmp
                }
                break
            }
        }
    }

    /**
     * Downwards fix starting from a particular element at a maximum level.
     * Performs comparisons using the comparator.
     *
     * @param k
     * the index of the starting element
     */
    private fun fixdownMaxWithComparator(k: Int) {
        var k: Int = k
        var c: Int = 2 * k
        while (c <= size) {
            val m: Int = maxChildOrGrandchildWithComparator(k)
            if (m > c + 1) { // grandchild
                if (comparator!!.compare(array[m], array[ k ]) <= 0) {
                    break
                }
                var tmp= array[ k ]
                array[ k ] = array[m]
                array[m] = tmp
                if (comparator.compare(array[m], array[m / 2]) < 0) {
                    tmp = array[m]
                    array[m] = array[m / 2]
                    array[m / 2] = tmp
                }
                // go down
                k = m
                c = 2 * k
            } else { // child
                if (comparator!!.compare(array[m], array[ k ]) > 0) {
                    val tmp = array[ k ]
                    array[ k ] = array[m]
                    array[m] = tmp
                }
                break
            }
        }
    }

    /**
     * Return true if on a minimum level, false otherwise.
     *
     * @param k
     * the element
     * @return true if on a minimum level, false otherwise
     */
    @VisibleForTesting
    fun onMinLevel(k: Int): Boolean {
        val kAsFloat: Float = k.toFloat()
        val exponent: Int = Math.getExponent(kAsFloat)
        return exponent % 2 == 0
    }

    /**
     * Given a node at a maximum level, find its child or grandchild with the
     * maximum key. This method should not be called for a node which has no
     * children.
     *
     * @param k
     * a node at a maximum level
     * @return the child or grandchild with a maximum key, or undefined if there
     * are no children
     */
    private fun maxChildOrGrandchild(k: Int): Int {
        var gc: Int = 4 * k
        var maxgc: Int
        var gcValue: K

        // 4 grandchilden
        if (gc + 3 <= size) {
            gcValue = array[gc]!!
            maxgc = gc
            if ((array[++gc] as Comparable<K>).compareTo(gcValue) > 0) {
                gcValue = array[gc]!!
                maxgc = gc
            }
            if ((array[++gc] as Comparable<K>).compareTo(gcValue) > 0) {
                gcValue = array[gc]!!
                maxgc = gc
            }
            if ((array[++gc] as Comparable<K>).compareTo(gcValue) > 0) {
                maxgc = gc
            }
            return maxgc
        }

        when (size - gc) {
            2 -> {
                // 3 grandchildren, two children
                gcValue = array[gc]!!
                maxgc = gc
                if ((array[++gc] as Comparable<K>).compareTo(gcValue) > 0) {
                    gcValue = array[gc]!!
                    maxgc = gc
                }
                if ((array[++gc] as Comparable<K>).compareTo(gcValue) > 0) {
                    maxgc = gc
                }
                return maxgc
            }

            1 -> {
                // 2 grandchildren, maybe two children
                gcValue = array[gc]!!
                maxgc = gc
                if ((array[++gc] as Comparable<K>).compareTo(gcValue) > 0) {
                    gcValue = array[gc]!!
                    maxgc = gc
                }
                if (2 * k + 1 <= size && (array[2 * k + 1] as Comparable<K>).compareTo(gcValue) > 0) {
                    maxgc = 2 * k + 1
                }
                return maxgc
            }

            0 -> {
                // 1 grandchild, maybe two children
                gcValue = array[gc]!!
                maxgc = gc
                if (2 * k + 1 <= size && (array[2 * k + 1] as Comparable<K>).compareTo(gcValue) > 0) {
                    maxgc = 2 * k + 1
                }
                return maxgc
            }
        }
        // 0 grandchildren
        maxgc = 2 * k
        gcValue = array[maxgc]!!
        if (2 * k + 1 <= size && (array[2 * k + 1] as Comparable<K>).compareTo(gcValue) > 0) {
            maxgc = 2 * k + 1
        }
        return maxgc
    }

    /**
     * Given a node at a maximum level, find its child or grandchild with the
     * maximum key. This method should not be called for a node which has no
     * children.
     *
     * @param k
     * a node at a maximum level
     * @return the child or grandchild with a maximum key, or undefined if there
     * are no children
     */
    private fun maxChildOrGrandchildWithComparator(k: Int): Int {
        var gc: Int = 4 * k
        var maxgc: Int
        var gcValue: K

        // 4 grandchilden
        if (gc + 3 <= size) {
            gcValue = array[gc]!!
            maxgc = gc
            if (comparator!!.compare(array[++gc], gcValue) > 0) {
                gcValue = array[gc]!!
                maxgc = gc
            }
            if (comparator.compare(array[++gc], gcValue) > 0) {
                gcValue = array[gc]!!
                maxgc = gc
            }
            if (comparator.compare(array[++gc], gcValue) > 0) {
                maxgc = gc
            }
            return maxgc
        }

        when (size - gc) {
            2 -> {
                // 3 grandchildren, two children
                gcValue = array[gc]!!
                maxgc = gc
                if (comparator!!.compare(array[++gc], gcValue) > 0) {
                    gcValue = array[gc]!!
                    maxgc = gc
                }
                if (comparator.compare(array[++gc], gcValue) > 0) {
                    maxgc = gc
                }
                return maxgc
            }

            1 -> {
                // 2 grandchildren, maybe two children
                gcValue = array[gc]!!
                maxgc = gc
                if (comparator!!.compare(array[++gc], gcValue) > 0) {
                    gcValue = array[gc]!!
                    maxgc = gc
                }
                if (2 * k + 1 <= size && comparator.compare(array[2 * k + 1], gcValue) > 0) {
                    maxgc = 2 * k + 1
                }
                return maxgc
            }

            0 -> {
                // 1 grandchild, maybe two children
                gcValue = array[gc]!!
                maxgc = gc
                if (2 * k + 1 <= size && comparator!!.compare(array[2 * k + 1], gcValue) > 0) {
                    maxgc = 2 * k + 1
                }
                return maxgc
            }
        }
        // 0 grandchildren
        maxgc = 2 * k
        gcValue = array[maxgc]!!
        if (2 * k + 1 <= size && comparator!!.compare(array[2 * k + 1], gcValue) > 0) {
            maxgc = 2 * k + 1
        }
        return maxgc
    }

    /**
     * Given a node at a minimum level, find its child or grandchild with the
     * minimum key. This method should not be called for a node which has no
     * children.
     *
     * @param k
     * a node at a minimum level
     * @return the child or grandchild with a minimum key, or undefined if there
     * are no children
     */
    private fun minChildOrGrandchild(k: Int): Int {
        var gc: Int = 4 * k
        var mingc: Int
        var gcValue: K

        // 4 grandchilden
        if (gc + 3 <= size) {
            gcValue = array[gc]!!
            mingc = gc
            if ((array[++gc] as Comparable<K>).compareTo(gcValue) < 0) {
                gcValue = array[gc]!!
                mingc = gc
            }
            if ((array[++gc] as Comparable<K>).compareTo(gcValue) < 0) {
                gcValue = array[gc]!!
                mingc = gc
            }
            if ((array[++gc] as Comparable<K>).compareTo(gcValue) < 0) {
                mingc = gc
            }
            return mingc
        }

        when (size - gc) {
            2 -> {
                // 3 grandchildren, two children
                gcValue = array[gc]!!
                mingc = gc
                if ((array[++gc] as Comparable<K>).compareTo(gcValue) < 0) {
                    gcValue = array[gc]!!
                    mingc = gc
                }
                if ((array[++gc] as Comparable<K>).compareTo(gcValue) < 0) {
                    mingc = gc
                }
                return mingc
            }

            1 -> {
                // 2 grandchildren, maybe two children
                gcValue = array[gc]!!
                mingc = gc
                if ((array[++gc] as Comparable<K>).compareTo(gcValue) < 0) {
                    gcValue = array[gc]!!
                    mingc = gc
                }
                if (2 * k + 1 <= size && (array[2 * k + 1] as Comparable<K>).compareTo(gcValue) < 0) {
                    mingc = 2 * k + 1
                }
                return mingc
            }

            0 -> {
                // 1 grandchild, maybe two children
                gcValue = array[gc]!!
                mingc = gc
                if (2 * k + 1 <= size && (array[2 * k + 1] as Comparable<K>).compareTo(gcValue) < 0) {
                    mingc = 2 * k + 1
                }
                return mingc
            }
        }
        // 0 grandchildren
        mingc = 2 * k
        gcValue = array[mingc]!!
        if (2 * k + 1 <= size && (array[2 * k + 1] as Comparable<K>).compareTo(gcValue) < 0) {
            mingc = 2 * k + 1
        }
        return mingc
    }

    /**
     * Given a node at a minimum level, find its child or grandchild with the
     * minimum key. This method should not be called for a node which has no
     * children.
     *
     * @param k
     * a node at a minimum level
     * @return the child or grandchild with a minimum key, or undefined if there
     * are no children
     */
    private fun minChildOrGrandchildWithComparator(k: Int): Int {
        var gc: Int = 4 * k
        var mingc: Int
        var gcValue: K

        // 4 grandchilden
        if (gc + 3 <= size) {
            gcValue = array[gc]!!
            mingc = gc
            if (comparator!!.compare(array[++gc], gcValue) < 0) {
                gcValue = array[gc]!!
                mingc = gc
            }
            if (comparator.compare(array[++gc], gcValue) < 0) {
                gcValue = array[gc]!!
                mingc = gc
            }
            if (comparator.compare(array[++gc], gcValue) < 0) {
                mingc = gc
            }
            return mingc
        }

        when (size - gc) {
            2 -> {
                // 3 grandchildren, two children
                gcValue = array[gc]!!
                mingc = gc
                if (comparator!!.compare(array[++gc], gcValue) < 0) {
                    gcValue = array[gc]!!
                    mingc = gc
                }
                if (comparator.compare(array[++gc], gcValue) < 0) {
                    mingc = gc
                }
                return mingc
            }

            1 -> {
                // 2 grandchildren, maybe two children
                gcValue = array[gc]!!
                mingc = gc
                if (comparator!!.compare(array[++gc], gcValue) < 0) {
                    gcValue = array[gc]!!
                    mingc = gc
                }
                if (2 * k + 1 <= size && comparator.compare(array[2 * k + 1], gcValue) < 0) {
                    mingc = 2 * k + 1
                }
                return mingc
            }

            0 -> {
                // 1 grandchild, maybe two children
                gcValue = array[gc]!!
                mingc = gc
                if (2 * k + 1 <= size && comparator!!.compare(array[2 * k + 1], gcValue) < 0) {
                    mingc = 2 * k + 1
                }
                return mingc
            }
        }
        // 0 grandchildren
        mingc = 2 * k
        gcValue = array[mingc]!!
        if (2 * k + 1 <= size && comparator!!.compare(array[2 * k + 1], gcValue) < 0) {
            mingc = 2 * k + 1
        }
        return mingc
    }

    companion object {
        private val serialVersionUID: Long = -8985374211686556917L

        /**
         * Default initial capacity of the heap.
         */
        val DEFAULT_HEAP_CAPACITY: Int = 16

        /**
         * Create a heap from an array of elements. The elements of the array are
         * not destroyed. The method has linear time complexity.
         *
         * @param <K>
         * the type of keys maintained by the heap
         * @param array
         * an array of elements
         * @return a heap
         * @throws IllegalArgumentException
         * in case the array is null
        </K> */
        @JvmStatic
        @LinearTime
        fun <K> heapify(array: Array<K>): MinMaxBinaryArrayDoubleEndedHeap<K> {
            if (array == null) {
                throw IllegalArgumentException("Array cannot be null")
            }
            if (array.isEmpty()) {
                return MinMaxBinaryArrayDoubleEndedHeap()
            }

            val h: MinMaxBinaryArrayDoubleEndedHeap<K> = MinMaxBinaryArrayDoubleEndedHeap(array.size)

            System.arraycopy(array, 0, h.array, 1, array.size)
            h.size = array.size

            for (i in array.size / 2 downTo 1) {
                h.fixdown(i)
            }

            return h
        }

        /**
         * Create a heap from an array of elements. The elements of the array are
         * not destroyed. The method has linear time complexity.
         *
         * @param <K>
         * the type of keys maintained by the heap
         * @param array
         * an array of elements
         * @param comparator
         * the comparator to use
         * @return a heap
         * @throws IllegalArgumentException
         * in case the array is null
        </K> */
        @LinearTime
        fun <K> heapify(array: Array<K>, comparator: Comparator<in K?>?): MinMaxBinaryArrayDoubleEndedHeap<K> {
            if (array == null) {
                throw IllegalArgumentException("Array cannot be null")
            }
            if (array.isEmpty()) {
                return MinMaxBinaryArrayDoubleEndedHeap(comparator)
            }

            val h: MinMaxBinaryArrayDoubleEndedHeap<K> = MinMaxBinaryArrayDoubleEndedHeap(comparator, array.size)

            System.arraycopy(array, 0, h.array, 1, array.size)
            h.size = array.size

            for (i in array.size / 2 downTo 1) {
                h.fixdownWithComparator(i)
            }

            return h
        }
    }
}
